/*
https://leetcode.cn/problems/rotated-digits/submissions/568235232/
*/
class Solution {
    int diffs[10]={0,0,1,-1,-1,1,1,-1,0,1};
public:
    int rotatedDigits(int n) {
        string s=to_string(n);
        int m=s.length();
        int dp[m][2];
        memset(dp,-1,sizeof(dp));
        function<int(int,bool,bool)>dfs=[&](int i,bool has_diff,bool is_limit)->int{
            if(i==m) return has_diff;
            if(!is_limit&&dp[i][has_diff]>=0) return dp[i][has_diff];
            int res=0;
            int up=is_limit?s[i]-'0':9;
            for(int d=0;d<=up;++d)
                if(diffs[d]!=-1){
                    res+=dfs(i+1,has_diff||diffs[d],is_limit&&d==up);
                }
                if(!is_limit) dp[i][has_diff]=res;
                return res;
            };
            return dfs(0,false,true);
        }
};